/**
* @description: 813. 最大平均值和的分组
* @author hewei
* @date 2022/8/29 14:53
* @version 1.0
*/

public class LargestSumOfAverages {

    public double largestSumOfAverages(int[] nums, int k) {
        double[][] dp = new double[nums.length][k + 1];
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            dp[i][1] = (double) sum / (i + 1);
        }
        for (int i = 1; i < nums.length; i++) {
            for (int j = 2; j <= Math.min(i + 1, k); j++) {
                double max = 0;
                int temp = 0;
                for (int l = i - 1; l >= j - 2; l--) {
                    temp += nums[l + 1];
                    max = Math.max(max, dp[l][j - 1] + (double) temp / (i - l));
                }
                dp[i][j] = max;
            }
        }
        return dp[nums.length - 1][k];
    }
}
